AlgorithmsDivide and Conquer

Quicksort(퀵정렬)

분할정복법, 알고리즘

Quicksort is similar to Mergesort in that the sort is accomplished by dividing the array into two partitions and then sorting each partition recursively. However, in quicksort, the array is partitioned by placing all items smaller than some pivot item before that item and all items larger than the pivot item after it. The pivot item can be any item, and for convenience we will simply make it the first one.

퀵정렬은 선택된 피벗값을 기준으로 배열을 두 개의 파티션으로 나누고 재귀를 이용하여 각 파티션을 정렬한다는 점에서 합병정렬과 비슷하나, 정렬과정에서 추가적인 작업공간을 필요로 하지 않는다. 즉, 퀵정렬은 in-place sort이다.

Example The steps done by a human when sorting with Quicksort.


Quicksort Algorithm

Algorithm Design

  1. Partition the array so that all items smaller than the pivot item are to the left of it and all items larger are to the right.
  2. Sort the subarrays.

선택된 피벗 값을 기준으로 피벗보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 오도록 배열을 분할하고 각 부분배열을 정렬한다.

Pseudo Code

void quicksort(index low, index high)
{
  index pivotpoint;

  if (high > low) {
    partition(low, high, pivotpoint);
    quicksort(low, pivotpoint-1);
    quicksort(pivotpoint+1, high);
  }
}

void partition(index low, index high, index& pivotpoint)
{
  index i, j;
  keytype pivotitem;

  pivotitem = S[low]; // Choose first item for pivotitem.
  j = low;
  for (i = low+1; i <= high; i++)
    if (S[i] < pivotitem) {
      j++;
      exchange S[i] and S[j];
    }
    pivotpoint = j;
    exchange S[low] and S[pivotpoint]; // Put pivotitem at pivotpoint.
}

Source Code

// File: sorting.h
#ifndef SORTING_H
#define SORTING_H

namespace algorithms
{
  void quicksort(int data[ ], int low, int high);
  // Problem: Sort n keys in nondecreasing order.
  // Inputs: positive integer n, array of keys S indexed from 1 to n.
  // Outputs: the array S containing the keys in nondecreasing order.

  void partition(int data[ ], int low, int high, int& pivotpoint);
  // Problem: Partition the array S for Quicksort.
  // Inputs: two indices, low and high, and the subarray of S indexed
  // from low to high.
  // Outputs: pivotpoint, the pivot point for the subarray indexed
  // from low to high.
}

#endif
// File: sorting.cpp
#include <algorithm> // Provides swap
#include "sorting.h"

namespace algorithms
{
  void quicksort(int data[ ], int low, int high)
  {
    int pivotpoint;

    if (high > low)
    {
      partition(data, low, high, pivotpoint);
      quicksort(data, low, pivotpoint-1);  // before the pivotpoint
      quicksort(data, pivotpoint+1, high); // after the pivotpoint
    }
  }

  void partition(int data[ ], int low, int high, int& pivotpoint)
  {
    int i, j;
    int pivotitem;

    pivotitem = data[low]; // Choose first item for pivotitem.
    j = low;
    for (i = low+1; i <= high; ++i)
    {
      if (data[i] < pivotitem)
      {
        ++j;
        std::swap(data[i], data[j]);
      }
    }
    pivotpoint = j;
    std::swap(data[low], data[pivotpoint]); // Put pivotitem at pivotpoint.
  }
}
// File: sorttest.cpp
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include "sorting.h" // Provides sorting functions.
using namespace std;
using namespace algorithms;

// PROTOTYPE of a function that will test one of the sorting functions:
void testsort(void sorter(int data[ ], int start, int last),
         const char* file_name, const char* sorting_name);

void open_for_read(ifstream& f, const char filename[ ]);
// Postcondition: The ifstream f has been opened for reading using the given
// filename. If any errors occurred then an error message has been printed
// and the program has been halted.

bool is_more(istream& source);
// Precondition: input is an open istream.
// Postcondition: The return value is true if input still has more data to
// read; otherwise the return value is false.

void process_read(ifstream& f, int data[ ]);
// Precondition: input is an open istream.
// Postcondition: The values in inputfile are assigned to data array.

int main(int argc, char* argv[ ])
{  
  assert(argc == 2);
  testsort(quicksort, argv[1], "quicksort");

  return EXIT_SUCCESS;
}

void testsort(void sorter(int data[ ], int start, int last),
         const char* file_name, const char* sorting_name)
{

  const int ARRAY_SIZE = 100000;
  int data[ARRAY_SIZE];
  ifstream infile;

  open_for_read(infile, file_name);
  process_read(infile, data);
  infile.close( );

  clock_t start, end;  
  cout << "Testing the " << sorting_name << endl;
  start = clock( );
  sorter(data, 0, ARRAY_SIZE-1); // Sort the numbers
  end = clock( );

  // Check the sorting result.
  for (int i = 1; i < ARRAY_SIZE; ++i)
  {
    if (data[i-1] > data[i])
      exit(0);
  }
  cout << "Sorting completed correctly." << endl;
  double result = (double)(end-start) / CLOCKS_PER_SEC;
  cout << sorting_name << "'s elpased time is : "<< result << " sec." << endl;
}

void open_for_read(ifstream& f, const char filename[ ])
{
  f.open(filename);

  if (f.fail( ))
  {
    cerr << "Could not open input file." << endl;
    exit(0);
  }
}

bool is_more(ifstream& source)
{
  return (source && source.peek( ) != EOF);
}

void process_read(ifstream& f, int data[ ])
{
  size_t index = 0;

  while (is_more(f))
  {
    assert(f);
    f >> data[index];
    ++index;
  }
}


Time Complexity Analysis

Basic operation

  • the comparison of S[i] with pivotitem in partition.

Input size

  • n, the number of items in the array S.

Worst-Case Time Complexity

  • $W(n) = \frac{n(n-1)}{2} \in \Theta (n^2)$

Average-Case Time Complexity

  • $A(n) \approx 1.38(n+1)logn \in \Theta (nlogn)$

시간복잡도가 최악인 경우, 퀵정렬의 비교횟수는 n^2(quadratic time)을 요구한다. 하지만 정렬하고자 하는 키값들이 무작위로 분산되어 있다면, 평균적으로 퀵정렬이 수행하는 비교횟수는 nlogn에 비례한다.

퀵정렬의 성능향상을 위해서는 중간값에 가까운 피벗을 선택해야 한다. 선택된 피벗이 중간값에 가까울수록 좌우 파티션이 균등하게 이루어져 더 빨리 정렬할 수 있다.

위의 예시처럼 첫번째 항목을 피벗으로 잡는건 효율적이라고 할 수 없다. 피벗값 선택시 랜덤하게 3~5개의 원소를 선택 한 후, 그 중에서 중간값을 취하는 방법도 있다.

Share